1. Field of Invention
The field of this invention is cryptography. This invention relates to digital signature schemes, and in particular to schemes that are compatible with auto-recoverable (also interchangeably called auto-escrowable) and auto-certifiable cryptosystems. The invention enables the implementation of a public key infrastructure (PKI) where the authorities can read selectively chosen encrypted messages, but cannot forge digital signatures, while each user possesses a single public key. The scheme introduces the notion of a three-key cryptosystem. This system involves the use of a private signing key, a private decryption key, and a single public key which is good for encrypting data and for signature verification. The device has the property that the private signing key is not escrowed, while the private decryption key is and the private signing key is not derivable from the private decryption key. The invention relates to cryptosystems implemented in software, but is also applicable to cryptosystems implemented in hardware.
2. Description of Prior Art
Public Key Cryptosystems (PKC's) allow secure communications between two parties who have never met before. The notion of a PKC was put forth in (W. Diffie, M. Hellman, "New directions in cryptography", IEEE Transactions on Information Theory, 22, pages 644-654, 1976). This communication can take place over an insecure channel. In a PKC, each user possesses a public key E and a private key D. E is made publicly available by a key distribution center, also called certification authority (CA), after the registration authority verifies the authenticity of the user (its identification, etc.). The registration authority is part of the certification authority. D is kept private by the user. E is used to encrypt messages, and only D can be used to decrypt messages. It is computationally impossible to derive D from E. To use a PKC, party A obtains party B's public key E from the key distribution center. Party A encrypts a message with E and sends the result to party B. B recovers the message by decrypting with D. The key distribution center is trusted by both parties to give correct public keys upon request. In the same paper by Diffie and Hellman the notion of a digital signature scheme was also proposed. A digital signature scheme allows a user to digitally "sign" a message using the private key known only to the user, to prove that the message comes from the user. For singatures, E is used to verify signatures and D is used to sign messages. To send a signature of message m, A applies its D function to the message and sends the result to user B. User B obtains A's public key E from the key distribution center and applies E to verify A's signature. The first public key cryptosystem and signature scheme is the RSA scheme (U.S. Pat. No. 4,405,829). A PKC and digital signature scheme based on the difficulty of computing discrete logarithms was published in (T. ElGamal, "A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms", CRYPTO '84, pages 10-18, Springer-Verlag, 1985).
The Digital Signature Algorithm (DSA) is a discrete log based signature scheme that is patented (U.S. Pat. No. 5,231,668). DSA gets its security from the difficulty of computing discrete logs modulo the prime p, where p is at least 512 bits in size. It also gets its security from the difficulty of computing discrete logs in a cyclic subgroup of order q, where q is a 160 bit prime divisor of p-1. DSA outputs signatures that are 320 bits in length. The schnorr digital signature scheme is another discrete log based signature scheme (U.S. Pat. No. 4,995,082). Nyberg and Rueppel disclosed a set of ElGamal based variants that provide for message recovery (K. Nyberg, R. Rueppel, "Message Recovery for Signature Schemes Based on the Discrete Logarithm Problem, Eurocrypt '94, pages 182-193, 1994). The message recovery feature allows the message to be recovered from the signature itself, hence the message need not be sent along with the signature. Another important feature of digital signature schemes is blindability (D. Chaum, "Blind Signatures for Untraceable Payments", CRYPTO '82, pages 199-203). A scheme is blindable if it is possible for Alice to obtain a Bob's signature on a message of her choice such that Bob remains oblivious as to what he is signing and what the resulting signature is. In (D. Chaum, T. Pedersen, "Wallet Databases with Observers", CRYPTO '92, pages 89-105) a blindable scheme based on ElGamal is disclosed. A good overview of digital signature security is described in (S. Goldwasser, S. Micali, R. Rivest, "A digital Signature Scheme Secure Against Adaptive Chosen Message Attacks", SIAM J. Comput., vol. 17, n. 2, pages 281-308, 1988). Other signatures schemes are described in (B. Schneier, Applied Cryptography, 2nd edition, Wiley & Sons) and in (Menezes, Oorshot, Vanstone, "CRC Handbook of Applied Cryptography", pages 425-481).
In the pending U.S. Patent Application of Young and Yung entitled "Auto-escrowable and Auto-Certifiable Cryptosystems" (filed May 1997), a public key cryptosystem was disclosed that has the following properties. Users of the system can generate a public/private key pair and a certificate of recoverability. This certificate of recoverability can be used to both recover the private key by the escrow authorities, and verify that the private key is recoverable. The present invention draws many of its ideas from the Auto-Escrowable and Auto-Certifiable key escrow solution. Other methods for conducting key escrow are U.S. Pat. Nos. 5,276,737, and 5,315,658 which are due to Micali (1994). In these patents Micali discloses a Fair Public Key Cryptosystem (FPKC) which is based on the work of P. Feldman (28th annual FOCS). The FPKC solution is not as efficient in terms of use as Auto-Escrowable and Auto-Certifiable Cryptosystems. Furthermore, It has been shown that the Fair RSA PKC does not meet certain needs of law enforcement (J. Kilian, F. Leighton, "Fair Cryptosystems Revisited", CRYPTO '95, pages 208-221, Springer-Verlag, 1995), since a shadow public key cryptosystem can be embedded within it. A shadow public key system is a system that can be embedded in a key escrow system that permits conspiring users to conduct untappable communications. Kilian and Leighton disclose a Fail-safe Key Escrow system. This system has the drawback that it requires users to engage in a multi-round protocol in order to generate public/private key pairs. Other key escrow systems with similar inneficiencies are by De Santis et al., Walker and Winston (TIS), and the IBM SecureWay document. A "Fraud-Detectable Alternative to Key-Escrow Proposals" based on ElGamal has been described in (E. Verheul, H. van Tilborg, "Binding ElGamal: A Fraud-Detectable Alternative to Key-Escrow Proposals", Eurocrypt '97, pages 119-133, Springer-Verlag, 1997). This system provides for session level key recoverability, and makes no provision for preventing users from encrypting messages prior to using the Binding ElGamal system. Hence, it permits conspiring criminals to conduct untappable communicatinos. Both Binding ElGamal and the Auto-Escrowable and Auto-Certifiable Cryptosystems solutions employ the use of non-interactive zero-knowledge proofs. More specificly, they employ the Fiat Shamir heuristic which is disclosed in (A. Fiat, A. Shamir, "How to Prove Yourself: Practical Solutions to Identification and Signature Problems", CRYPTO '86, pages 186-194, Springer-Verlag, 1987). An overview of key escrow schemes appears in (D. Denning, D. Branstad, "A Taxonomy for Key Escrow Encryption Systems," Communications of the ACM, v. 39, n. 3, 1996). In (N. Jefferies, C. Mitchell, M. Walker, "A Proposed Architecture for Trusted Third Party Services", Cryptography: Policy and Algorithms, LNCS 1029, Springer, 1996) and (R. Anderson, "The GCHQ Protocol and Its Problems", Eurocrypt '97, pages 134-148, Springer-Verlag, 1997) a trusted third party approach to escrow is described where the trusted third parties of the participating users are involved in every session key establishment stage, and hence provides for another encumbersome solution as well.
The primary problem with implementing a digital signature scheme suitable for use with an escrow system is that very often the public signature verification key can be used as a public encryption key, and the corresponding private signing key can be used as a private decryption key. This is a problem because law enforcement sometimes has the need to be able to decrypt messages, and if messages are encrypted using a public signature verification key, then law enforcement needs to be able to have access to the corresponding private signing key. But this implies that law enforcement will have access to signature keys, and thus law enforcement has the ability to forge signatures of users. It also implies that law enforcement can impersonate users in interactive identification protocols and user authentication protocols. There is no legitimate reason that law enforcement should have this capability. This problem is discussed in (Y. Frankel, M. Yung, "Escrow Encryption Systems Visited: Attacks, Analysis and Designs", CRYPTO '95, pages 222-235, Springer-Verlag, 1995) and (R. Anderson, "The GCHQ Protocol and Its Problems", Eurocrypt '97, pages 134-148, Springer-Verlag, 1997). Hence, what is needed to enable authentication in an escrow system is a public and private key system that has the properties that (1) opening the decryption key does not enable a signing capability, and (2) the signing capability does not enable decryption.